import java.util.*;

public class Main {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            inorderRecursive(root, result);
            return result;
        }

        private void inorderRecursive(TreeNode node, List<Integer> result) {
            if (node == null) {
                return;
            }
            inorderRecursive(node.left, result);
            result.add(node.val);
            inorderRecursive(node.right, result);
        }
    }

    class Solution2 {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            preorderRecursive(root, result);
            return result;
        }

        private void preorderRecursive(TreeNode node, List<Integer> result) {
            if (node == null) {
                return;
            }
            result.add(node.val);
            preorderRecursive(node.left, result);
            preorderRecursive(node.right, result);
        }
    }

    class Solution3 {
        private Map<Integer, Integer> inorderMap;
        private int[] postorder;
        private int postIndex;

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            int n = inorder.length;
            this.postorder = postorder;
            this.postIndex = n - 1;

            inorderMap = new HashMap<>();
            for (int i = 0; i < n; i++) {
                inorderMap.put(inorder[i], i);
            }

            return build(0, n - 1);
        }

        private TreeNode build(int inLeft, int inRight) {
            if (inLeft > inRight) {
                return null;
            }

            int rootVal = postorder[postIndex];
            TreeNode root = new TreeNode(rootVal);

            int rootIndex = inorderMap.get(rootVal);
            postIndex--;

            root.right = build(rootIndex + 1, inRight);
            root.left = build(inLeft, rootIndex - 1);

            return root;
        }
    }

    class Solution4 {
        private Map<Integer, Integer> inorderIndexMap;
        private int[] preorder;
        private int preIndex;

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            this.preIndex = 0;

            inorderIndexMap = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) {
                inorderIndexMap.put(inorder[i], i);
            }

            return build(0, inorder.length - 1);
        }

        private TreeNode build(int inLeft, int inRight) {
            if (inLeft > inRight) {
                return null;
            }

            int rootVal = preorder[preIndex];
            TreeNode root = new TreeNode(rootVal);

            preIndex++;

            int rootInIndex = inorderIndexMap.get(rootVal);

            root.left = build(inLeft, rootInIndex - 1);
            root.right = build(rootInIndex + 1, inRight);

            return root;
        }
    }

    class Solution5 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q) {
                return root;
            }

            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);

            if (left == null) {
                return right;
            }
            if (right == null) {
                return left;
            }
            return root;
        }
    }

    class Solution6 {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) {
                return result;
            }

            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);

            while (!queue.isEmpty()) {
                int levelSize = queue.size();
                List<Integer> currentLevel = new ArrayList<>();

                for (int i = 0; i < levelSize; i++) {
                    TreeNode node = queue.poll();
                    currentLevel.add(node.val);

                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                }

                result.add(currentLevel);
            }

            Collections.reverse(result);
            return result;
        }
    }

    class Solution7 {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) {
                return result;
            }

            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);

            while (!queue.isEmpty()) {
                int levelSize = queue.size();
                List<Integer> currentLevel = new ArrayList<>();
                for (int i = 0; i < levelSize; i++) {
                    TreeNode node = queue.poll();
                    currentLevel.add(node.val);

                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                }
                result.add(currentLevel);
            }
            return result;
        }
    }

    class Solution8 {
        public String tree2str(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            preorder(root, sb);
            return sb.toString();
        }
        private void preorder(TreeNode node, StringBuilder sb) {
            if (node == null) {
                return;
            }
            sb.append(node.val);
            if (node.left != null || node.right != null) {
                sb.append('(');
                preorder(node.left, sb);
                sb.append(')');
                if (node.right != null) {
                    sb.append('(');
                    preorder(node.right, sb);
                    sb.append(')');
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("Hello, World!");
    }
}